By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

ALERT ATTENTION: System maintenance will be performed the weekend of Saturday, March 28, 2009. This event will begin at 6:00 am on March 28 and will conclude at approximately 12:00 noon on Sunday March 29 (all times EDT). Some Scitation services may be affected during this period.
Table of Contents
Search This Issue
Volume 31, Issue 4, pp. 989-1313

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

A Layered Analysis of Consensus

Yoram Moses and Sergio Rajsbaum

pp. 989-1021

BibTeX  Abstract Full Text:  PDF

On Binary Searching with Nonuniform Costs

Eduardo S. Laber, Ruy L. Milidiú, and Artur A. Pessoa

pp. 1022-1047

BibTeX  Abstract Full Text:  PDF

The Efficiency of Resolution and Davis--Putnam Procedures

Paul Beame, Richard Karp, Toniann Pitassi, and Michael Saks

pp. 1048-1075

BibTeX  Abstract Full Text:  PDF

A Decision Procedure for Unitary Linear Quantum Cellular Automata

Christoph Dürr and Miklos Santha

pp. 1076-1089

BibTeX  Abstract Full Text:  PDF

A Polylogarithmic Approximation of the Minimum Bisection

Uriel Feige and Robert Krauthgamer

pp. 1090-1118

BibTeX  Abstract Full Text:  PDF

Lattice Embeddings for Abstract Bounded Reducibilities

Wolfgang Merkle

pp. 1119-1155

BibTeX  Abstract Full Text:  PDF

Decidability of Termination of Grid String Rewriting Rules

Alfons Geser

pp. 1156-1168

BibTeX  Abstract Full Text:  PDF

Randomness, Computability, and Density

Rod G. Downey, Denis R. Hirschfeldt, and André Nies

pp. 1169-1183

BibTeX  Abstract Full Text:  PDF

Space Complexity in Propositional Calculus

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, and Avi Wigderson

pp. 1184-1211

BibTeX  Abstract Full Text:  PDF

An Enumerative Geometry Framework for Algorithmic Line Problems in $\mathbb R^3$

Thorsten Theobald

pp. 1212-1228

BibTeX  Abstract Full Text:  PDF

Quantum Circuits That Can Be Simulated Classically in Polynomial Time

Leslie G. Valiant

pp. 1229-1254

BibTeX  Abstract Full Text:  PDF

Finding Double Euler Trails of Planar Graphs in Linear Time

Zhi-Zhong Chen, Xin He, and Chun-Hsi Huang

pp. 1255-1285

BibTeX  Abstract Full Text:  PDF

The Combinatorial Structure of Wait-Free Solvable Tasks

Hagit Attiya and Sergio Rajsbaum

pp. 1286-1313

BibTeX  Abstract Full Text:  PDF